package com.mdnote.practice.linked_list;

import javax.swing.*;
import java.util.ArrayList;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/10/20
 * @description  143. 重排链表
 */
public class LeetCode143 {

    public static void main(String[] args) {
        LeetCode143 leetCode143 = new LeetCode143();

        ListNode listNode = new ListNode(11);
        listNode.next = new ListNode(12);
        listNode.next.next = new ListNode(13);
        listNode.next.next.next = new ListNode(14);
        listNode.next.next.next.next = new ListNode(15);
        leetCode143.reorderList(listNode);


        ListNode cur = listNode;
        while (cur != null) {
            System.out.println(cur.val);
            cur = cur.next;
        }
    }

    public void reorderList(ListNode head) {

        if (head == null) {
            return;
        }
//        reSortByList(head);
        reSortByMerge(head);



    }

    private void reSortByMerge(ListNode head) {

        // 找到中间节点
        ListNode midNode = selectMid(head);

        // 翻转后面的两边
        // 劈开
        ListNode temp = midNode.next;
        midNode.next = null;
        ListNode newNode = reverse(temp);
        // 合并
        mergeTo(head, newNode);
    }

    private void mergeTo(ListNode head, ListNode newNode) {

        ListNode node1 = head, node2 = newNode;

        while (node1 != null && node2 != null) {

            ListNode next1 = node1.next;
            ListNode next2 = node2.next;

            node1.next = node2;
            node2.next = next1;

            node1 = next1;
            node2 = next2;
        }

    }

    private ListNode reverse(ListNode node) {

        ListNode pre = null, cur = node, next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        };

        return pre;
    }

    private ListNode selectMid(ListNode head) {
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        return slow;
    }

    private void reSortByList(ListNode head) {

        ListNode cur = head;
        ArrayList<ListNode> nodeList = new ArrayList<>();
        while (cur != null) {
            nodeList.add(cur);
            cur = cur.next;
        }

        int i = 0, j = nodeList.size() - 1;
        while (i < j) {
            ListNode node = nodeList.get(i);
            // Step 1
            node.next = nodeList.get(j);
            i++;
            // 处理偶数
            if (i == j) {
                break;
            }
            // Step 2
            nodeList.get(j).next = nodeList.get(i);
            j--;
        }
        nodeList.get(i).next = null;
    }

    public static class ListNode {
         int val;
         ListNode next;
         ListNode() {}
         ListNode(int val) { this.val = val; }
         ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     }
}
